/*
 * Copyright (C), 2015-2018
 * FileName: Solution035
 * Author:   zhao
 * Date:     2018/8/16 22:45
 * Description: 搜索插入位置
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

/**
 * 〈一句话功能简述〉<br>
 * 〈搜索插入位置〉
 *
 * @author zhao
 * @date 2018/8/16 22:45
 * @since 1.0.0
 */
public class Solution035 {
  /**
   * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
   *
   * 你可以假设数组中无重复元素。
   *
   * 示例 1:
   *
   * 输入: [1,3,5,6], 5
   * 输出: 2
   * 示例 2:
   *
   * 输入: [1,3,5,6], 2
   * 输出: 1
   * 示例 3:
   *
   * 输入: [1,3,5,6], 7
   * 输出: 4
   * 示例 4:
   *
   * 输入: [1,3,5,6], 0
   * 输出: 0
   */

  /**
   * 想法：遍历数组，把target和当前位置数据进行对比，分析不同情况
   * 结果：超过80%的结果
   *
   * @param nums   数组
   * @param target 要插入的值
   * @return 插入位置
   */
  public int searchInsert(int[] nums, int target) {
    int result = -1;
    for (int i = 0; i < nums.length; i++) {
      if (target > nums[i]) {
        continue;
      }
      if (target == nums[i]) {
        result = i;
        break;
      }

      if (target < nums[i]) {
        result = i;
        break;
      }
    }

    if (result == -1) {
      result = nums.length;
    }

    return result;
  }

  /**
   * 这里使用了二分法查找
   *
   * @param nums   数组
   * @param target 要插入的值
   * @return 插入位置
   */
  public int better(int[] nums, int target) {
    //[0,len)开区间
    int i = 0, j = nums.length;

    //因为是前闭后开，i=j的时候，其实就是没有意义了
    while (i < j) {

      int mid = (i + j) / 2;
      if (nums[mid] == target) {
        return mid;
      }
      if (target < nums[mid]) {
        //因为开区间，刚好没有取到mid
        j = mid;
      } else {
        //闭区间，为了不取到mid，只能+1
        i = mid + 1;
      }

    }

    return j;
  }

}